/*************************************************************************
	> File Name: merge_list.cpp
	> Author: 
	> Mail: 
	> Created Time: 二 10/13 12:48:12 2015
 ************************************************************************/

/******************************************
 *归并排序的优化版本：
 *通过一个链接数组，把数值位置的变化记录到链接数组中；
 *现在假设前4个和后4个数已经排序好，则Link表一一对应的值如下：
 *例如0  1  2  3  4  5  6  7  8
 *arr:   50 10 25 30 15 70 35 55
 *Link:5  0  3  4  1  7  0  8  6
 *现在q指向2，前4个元素的最小值，r指向5，后4个元素最小值；
 *Link[1]=0 代表在前4个元素中对应的arr[1]=50为最大的元素，同理Link[2]=3代表在前4个元素中对应的
 *arr[2]=10的下一个元素是arr[3]，Link[3]=4代表arr[3]的下一个元素是arr[4]等，通过MergeL(2, 5, 5)
 *修改链接数组，里面存放着arr数组的排序。
 *****************************************/

#include<iostream>
using namespace std;

int arr[9] = {0,50,10,25,30,15,70,35,55};
int Link[9] = {0,0,0,0,0,0,0,0,0};

void MergeL(int, int, int&);

void MergeSortL(int low, int high, int &p) {
    if (low == high) {
        p = low;
    }
    else if (low < high){
        int q = 0;
        int r = 0;
        int mid = (low + high) / 2;
        MergeSortL(low, mid, q);
        MergeSortL(mid + 1, high, r);
        MergeL(q,r,p);
    }
}

void MergeL(int q, int r, int &p) {
    int i, j, k;
    i = q;
    j = r;
    k = 0;
    while ( (i != 0) && (j != 0) ) {
        if (arr[i] <= arr[j]) {
            Link[k] = i;
            k = i;
            i = Link[i];

        }
        else {
            Link[k] = j;
            k = j;
            j = Link[j];
        }
    }
    if (i == 0)
        Link[k] = j;
    if (j == 0)
        Link[k] = i;
    p = Link[0];
}

int main(void) {
    int p = 0;
    MergeSortL(1, 8, p);
    for (int i = 0; i < 9; ++i)
        cout << Link[i] << " ";
    cout << endl;
    int i = 0;
    while ( (i = Link[i]) != 0) {
        cout << arr[i] << " ";

    }
    cout << endl;
    return 0;
}
